package 算法.NiuKe.JZ;

import 算法.NiuKe.TreeNode;

import java.util.ArrayList;
import java.util.Stack;

/**
 * @author:谢君臣
 * @Date:2021/4/2720:54
 * @version:1.0
 * @function:   请实现一个函数按照之字形打印二叉树，即第一行按照从左到右的顺序打印，
 *       第二层按照从右至左的顺序打印，第三行按照从左到右的顺序打印，其他行以此类推。
 */
public class JZ60 {
    public ArrayList<ArrayList<Integer>> Print(TreeNode pRoot) {
        ArrayList<ArrayList<Integer>> res = new ArrayList<>();
        if (pRoot==null)
            return res;
        boolean flag = true;
        Stack<TreeNode> stack = new Stack<>();
        stack.push(pRoot);
        while (!stack.isEmpty()){
            ArrayList<Integer> list = new ArrayList<>();
            Stack<TreeNode> temp = new Stack<>();
            while (!stack.isEmpty()){
                TreeNode pop = stack.pop();
                if (flag){
                    if (pop.left!=null)temp.push(pop.left);
                    if (pop.right!=null)temp.push(pop.right);
                }else {
                    if (pop.right!=null)temp.push(pop.right);
                    if (pop.left!=null)temp.push(pop.left);
                }
                list.add(pop.val);
            }
            flag = !flag;
            stack = (Stack<TreeNode>) temp.clone();
            res.add(list);
        }
        return res;
    }
}
